/*
 * DepthLimitedSearch.java
 * 
 * Created on February 22, 2007, 7:54 PM
 *
 * Copyright 2008 David D. Emory
 * 
 * This file is part of Five Points. See <http://www.fpdev.org> for
 * additional information regarding the project.
 * 
 * Five Points is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Five Points is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Five Points.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.fpdev.core.algo;

import org.fpdev.core.basenet.BLink;
import org.fpdev.core.basenet.BaseNetGraph;
import org.fpdev.core.basenet.BNode;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import org.fpdev.core.basenet.*;

/**
 *
 * @author demory
 */
public class DepthLimitedSearch {

  //private Graph graph_;
  protected BaseNetGraph graph_;
  private int limit_;
  protected BNode lastSource_;
  private Map<Integer, PQLocator> inspected_;
  private Map<Integer, BLink> parentLinks_;
  private Set<BNode> visitedNodes_;
  private Set<BLink> visitedLinks_;
  private PriorityQueue<PQLocator> pq_;
  private Map<BNode, Integer> distances_;
  private int type_;
  //public static final int DIR_FW = 1;
  //public static final int DIR_BW = 2;
  public static final int TYPE_WALK = 1;
  public static final int TYPE_BIKE = 2;

  /** Creates a new instance of CLimitedDFS */
  public DepthLimitedSearch(BaseNetGraph graph, int type, int limit) {
    graph_ = graph;
    //System.out.println("lbfs graph rev = "+graph_.getIsReverse());
    type_ = type;
    limit_ = limit;

  //direction_ = DIR_FW;
  //System.out.println("Limit: "+limit);
  }

  //public void setDirection(int dir) { direction_ = dir; }
  public int weight(BLink link, BNode inNode) {
    return (int) graph_.getEdgeWeight(link, inNode);
  }

  public void nodeVisited(BNode node) {
  }

  public void execute(BNode source) {
    lastSource_ = source;
    pq_ = new PriorityQueue<PQLocator>(); //ArrayHeap(new IntegerComparator());
    distances_ = new HashMap<BNode, Integer>();
    inspected_ = new HashMap<Integer, PQLocator>();
    visitedNodes_ = new HashSet<BNode>();
    visitedLinks_ = new HashSet<BLink>();

    parentLinks_ = new HashMap<Integer, BLink>();
    //doOneIteration(source, 0);
    distances_.put(source, 0);
    inspect(source, null, 0);
    //visit(node);
    if (!hasTraversable(source)) {
      return;
    }
    while (!pq_.isEmpty()) {// && ((Integer)pq_.min().key()).intValue() < limit_ ) {
      //System.out.println("pq size = "+pq_.size());
      int nw = pq_.peek().getWeight();
      BNode node = pq_.poll().getNode(); //removeMin();
      if (distances_.get(node) < limit_) {
        visit(node, nw);
      }
    }
  }

  private boolean hasTraversable(BNode node) {
    Iterator<BLink> links = graph_.edgesOf(node).iterator();
    while (links.hasNext()) {
      BLink link = links.next();
      if (isTraversable(link, node)) {
        return true;
      }
    }
    return false;
  }

  private boolean isTraversable(BLink link, BNode inNode) {
    if (type_ == TYPE_WALK) {
      return link.isWalkable();
    }
    if (type_ == TYPE_BIKE) {
      return link.isBikeable(null);
    }//Bikeable(graph_.getIsReverse() ? graph_.opposite(inNode, link) : inNode);
    return false;
  }

  private void visit(BNode node, int nodeWeight) {
    //System.out.println("visit "+node.getID()+ " w="+nodeWeight);
    //Integer id = new Integer(node.getID());
    //int nodeWeight = ((Integer) inspected_.find(id).element()).intValue();
    visitedNodes_.add(node);
    nodeVisited(node);
    Iterator<BLink> links = graph_.edgesOf(node).iterator();
    //System.out.println("node "+node.getID()+" ("+inWeight+")");
    int inDist = distances_.get(node);
    while (links.hasNext()) {
      BLink link = links.next();
      //System.out.println(" link "+link.getID());

      if (isTraversable(link, node)) {
        BNode opp = graph_.opposite(node, link);

        // check distance
        if (!distances_.containsKey(opp)) {
          distances_.put(opp, inDist + link.getLengthFeet());
        } else if (inDist + link.getLengthFeet() < distances_.get(opp)) {
          distances_.put(opp, inDist + link.getLengthFeet());
        }

        int edgeWeight = weight(link, node); //direction_ == DIR_FW ? node : opp);
        inspect(opp, link, nodeWeight + edgeWeight);
      }
    }
  }

  private void inspect(BNode node, BLink parentLink, int w) {


    // check weight
    //Locator dLoc = inspected_.find(node.getID());
    if (!inspected_.containsKey(node.getID())) {
      Integer weight = new Integer(w);
      PQLocator pqLoc = new PQLocator(weight, node);
      pq_.offer(pqLoc);
      inspected_.put(node.getID(), pqLoc);
      if (parentLink != null) {
        parentLinks_.put(node.getID(), parentLink);
        visitedLinks_.add(parentLink);
      }
    } else {
      PQLocator pqLoc = inspected_.get(node.getID()); //(Locator) dLoc.element();
      int oldWeight = pqLoc.getWeight();
      if (w < oldWeight) {
        pq_.remove(pqLoc);
        PQLocator newPQLoc = new PQLocator(w, pqLoc.getNode());
        pq_.offer(newPQLoc);
        inspected_.put(node.getID(), newPQLoc);
        //pq_.replaceKey(pqLoc, new Integer(w));
        parentLinks_.put(node.getID(), parentLink);
      }
    }
  }

  public Iterator<BNode> visitedNodes() {
    return visitedNodes_.iterator();
  }

  public Iterator<BLink> visitedLinks() {
    return visitedLinks_.iterator();
  }

  public BLink getParentLink(BNode node) {
    return parentLinks_.get(node.getID());
  }

  public class PQLocator implements Comparable {

    private int weight_;
    private BNode node_;

    public PQLocator(int w, BNode n) {
      weight_ = w;
      node_ = n;
    }

    public int getWeight() {
      return weight_;
    }

    public BNode getNode() {
      return node_;
    }

    public int compareTo(Object o) {
      return new Integer(weight_).compareTo(((PQLocator) o).weight_);
    }
  }
}
